package dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 518. 零钱兑换 II
 */
public class P518 {
    public int change(int amount, int[] coins) {
        //每一个状态标识凑成该数值的组合数
        int[] dp = new int[amount + 1];
        for (int coin : coins) {
            if (coin <= amount) {
                dp[coin] += 1;
            }
        }
        for (int i = 1; i <= amount; i++) {
            Map<Integer, Integer> uniqueMap = new HashMap<>();
            for (int coin : coins) {
                if (i - coin > 0) {
                    if (!uniqueMap.containsKey(coin) || uniqueMap.get(coin) != (i - coin)) {
                        dp[i] += dp[i - coin];
                        uniqueMap.put(i - coin, coin);
                    }
                }
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(new P518().change(5, new int[]{1, 2, 5}));
    }
}
